package com.wfs.suanfa.leet;

/**
 * BM（Boyer-Moore）算法。它是一种非常高效的字符串匹配算法，有实验统计，它的性能是著名的KMP算法的3到4倍。
 * BM算法包含两部分，分别是坏字符规则（bad character rule）和好后缀规则（good suffix shift）
 * @author wfs
 * @date 2022-11-15 9:43
 */
public class BM {
    private static final int SIZE = 256; // 全局变量或成员变量

    public static void main(String[] args) {
        BM bm=new BM();
        char[] a="cabcab".toCharArray();
      //  int bm1 = bm.bm(a, 4, b, 3);
       // System.out.println(bm1);
        int[] suffix=new int[a.length];
        boolean[] prefix=new boolean[a.length];
        bm.generateGS(a,a.length,suffix,prefix);
        System.out.println();
    }

    /**
     * 假设字符串的字符集不是很大，每个字符长度是1字节，我们用大小为256的数组，来记录每个字符在模式串中出现的位置。数组的下标
     * 对应字符的ASCII码值，数组中存储这个字符在模式串中出现的位置。
     * @param b 模式串
     * @param m 模式串长度
     * @param bc 记录模式串中每个字符出现的位置
     */
    private void generateBC(char[] b,int m,int[] bc){
        for (int i = 0; i < SIZE; i++) {
            //初始化默认值
            bc[i]=-1;
        }
        for (int i = 0; i < m; i++) {
            int ascii=b[i];
            bc[ascii]=i;
        }
    }

    /**
     * @param a 主串
     * @param n 主串长度
     * @param b 模式串
     * @param m 模式串长度
     */
    public int bm(char[] a, int n, char[] b, int m) {
        // 记录模式串中每个字符最后出现的位置
        int[] bc = new int[SIZE];
        // 构建坏字符哈希表
        generateBC(b, m, bc);
        int[] suffix = new int[m];
        boolean[] prefix = new boolean[m];
        generateGS(b, m, suffix, prefix);
        // j表示主串与模式串匹配的第一个字符
        int i = 0;
        while (i <= n - m) {
            int j;
            // 模式串从后往前匹配
            for (j = m - 1; j >= 0; --j) {
                // 坏字符对应模式串中的下标是j
                if (a[i+j] != b[j]) break;
            }
            if (j < 0) {
                // 匹配成功，返回主串与模式串第一个匹配的字符的位置
                return i;
            }
            int x = j - bc[(int)a[i+j]];
            int y = 0;
            if (j < m-1) {
                // 如果有好后缀的话
                y = moveByGS(j, m, suffix, prefix);
            }
            i = i + Math.max(x, y);
        }
        return -1;
    }

    // j表示坏字符对应的模式串中的字符下标; m表示模式串长度
    private int moveByGS(int j, int m, int[] suffix, boolean[] prefix) {
        int k = m - 1 - j; // 好后缀长度
        if (suffix[k] != -1) return j - suffix[k] +1;
        for (int r = j+2; r <= m-1; ++r) {
            if (prefix[m-r] == true) {
                return r;
            }
        }
        return m;
    }

    /**
     * @param b 表示模式串
     * @param m 表示长度
     * @param suffix 如果suffix[k]不等于-1（-1表示不存在匹配的子串）那我们就将模式串往后移动j-suffix[k]+1位（j表示坏字符对应的模式串中的字符下标）。
     *               如果suffix[k]等于-1，表示模式串中不存在另一个跟好后缀匹配的子串片段。我们可以用下面这条规则来处理。
     */
    public void generateGS(char[] b,int m,int[] suffix,boolean[] prefix){
        // 初始化
        for (int i = 0; i < m; ++i) {
            suffix[i] = -1;
            prefix[i] = false;
        }
        for (int i = 0; i < m-1; i++) {
            int j=i;
            //公共后缀子串长度
            int k=0;
            //与b[0,m-1]求公共后缀子串
            while (j>=0 && b[j] == b[m-1-k]){
                --j;
                ++k;
                //表示公共后缀子串在b[0,i]中的起始下标
                suffix[k]=j+1;
            }
            //如果公共后缀子串也是模式串的前缀子串
            if (j==-1) prefix[k]=true;

        }
    }


}
